In today's information age, the ability to access rapidly data that is held in databases is of utmost importance to companies and organizations whose business may rely on the data. The speed with which a client is able to access data on a database relies on two major factors. The first factor is the speed with which the database file server can read data typically from a co-located repository which can be regarded as a storage device or as a storage system. This factor relies on the speed of the central processing unit (CPU) and on the disc access speed of the file server. The second factor is the capacity, or the bandwidth, of the communications link between the client and the file server.
A third factor effecting database access speed, which is extremely significant to the performance of an overall system, is the load on the system. The load is typically proportional to the number of clients which require database access. Both, the number of operations performed by the CPU and the volume of data which needs to be transmitted across communications links increases as more clients require database access.
System performance can be improved by increasing the speed of the file server and the bandwidth of the communications links. However, the related costs cannot always be justified. Also, there is always a limit to the speed at which current technologies can operate.
Another way of achieving better system performance, by reducing the database CPU and communications link load, is by using cached copies of the data. The cached copies are typically located physically nearer to the clients, or even on the client systems themselves. Indeed, this technique has been widely adopted on the internet by using internet file servers containing cached copies of the data located at ‘mirror sites’. For example, master data accessible from a master internet file server at a site in the USA might be copied or cached to a file server at a mirror site in the UK, from where a majority of European users might prefer to read the data. Thus, the data transfer overhead for transatlantic links and the demands placed on the master internet file server are reduced, and the overall perceived internet performance is improved. In particular, the European users would expect to obtain far better data access performance by using the UK mirror site.
The use of cached data does raise important issues concerning data consistency. It is sometimes difficult to know whether cached data is the same as the original, master data. The original data may change in some way after the cached copy is generated. In the case of the internet, for example, at present a lack of consistency between master data and cached data may not be of great significance and, if it is significant, it is usually possible to choose to retrieve the master data, albeit at a slower rate, from the master database.
Cache consistency, or coherency, is however extremely important in commercial environments where the data, whether cached or master, forms the basis for making business decisions. Inconsistent data, or data which takes too long to access, inevitably results in reduced revenue. A simple example of such an environment is one for making flight bookings, where, for example, the master flight data is held in a database in the UK and travel agencies around Europe book seats on flights on the basis of cached data. In this example, under most circumstances, it is essential that the cached data is consistent with the original data.
Similar considerations are important in a general multi-user system, for example based on client-server or distributed database, network environments, in which the user wherever possible rely on cached data to minimize CPU, data access, data transfer overheads imposed on master database file servers, and overall network traffic.
In, for example, a client-server environment having multiple clients accessing a single, master database file server, there is typically considerable opportunity to maintain with each client a large cache of recently read data. A cache may be used during an active transaction to avoid the need to re-read data from the master database. However, if data is cached on a client and the client needs to re-access that data at a later time, unless the data in the master database cannot change, it must be assumed that the data on the cache is inconsistent, because there is no way of knowing differently. Thus, further master database access is needed to at least compare the current state of data in the master database with the data in the cache database.
A decision whether or not to use data caching typically depends on the type of data to be accessed. WO 97/21177 mentions three common categories of data that are described below.
Static data, that is data which rarely changes, are prime candidates for holding in a client cache database. The data can always be assumed to be current. However, usually a task must be provided to ensure that changes to the static data are propagated to all client caches. This is typically done using an overnight batch process. For static data, there is no need for a real-time process to maintain consistency.
Highly dynamic data is difficult to maintain in a consistent state. The basic reason is that if the data changes very often, the network and processor impact, in a client-server environment, of up-dating many client caches can be considerable. In some cases, the cost in terms of processing overhead and network bandwidth of maintaining the caches might exceed the cost of each client accessing the master database directly each time data is required. Thus, this category of data would typically not be cached.
In between static and highly dynamic data is a type of data which is not static, but which changes relatively infrequently compared with highly dynamic data. Typically, in this case, data might only be cached onto a client cache database, for example at a travel agency, during the period of an aircraft flight enquiry and seat booking operation. Then, there would be a high degree of certainty that the data remains consistent during the operation. However, there would never be total certainty because, coincidentally, another client, or travel agency might book the only remaining seats on the respective flight between the times on which the first client started and completed its operation.
The simplest way to prevent data inconsistency, in for example the flight booking operation described above, would be to ‘lock’ any data on the master database which has been accessed by one client, thus making that data inaccessible, or at least only readable, to other clients for the whole period of the operation. This is called ‘pessimistic locking’. Typically, a lock table, which holds the identities of locked data which cannot be accessed or written to, is generated by the master file server. Such a system requires that all access requests made by clients invoke a lock table search on the file server before data access or writing is allowed, or denied.
However, in an environment where the same data might need to be accessed or up-dated by several clients, for example for flight-booking purposes, pessimistic locking represents an unworkable solution with intolerable locking overheads.
Another way of dealing with possible inconsistency between cached and master data is discussed in the book ‘Transaction Processing—Concepts and Techniques’ by J. Gray and A. Reuter, published by Morgan Kaufmann in 1993, on pages 434-435. The method involves ‘optimistic locking’.
Optimistic locking allows clients connected to a file server to use cached data at any time for reading purposes, but as soon as a transaction is initiated, for example making a flight seat booking, the cached data is compared with the master data to ensure data consistency and the master data is locked only for the period of the actual transaction. In this example, the transaction relates to the actual database access and to a write procedure. This prevents another client from changing the master data during the transaction. If, after the transaction has been initiated, the data in the cache database is found to be inconsistent with the corresponding data in the master database, the cache database is updated with the latest master data, and the client is notified and left to resolve any problems the inconsistency might have caused.
The advantage of optimistic locking is that the master data is only locked for a very short period of time, for maybe less than one second, to carry out the actual transaction. In contrast, pessimistic locking requires the data accessed to be locked for the whole period of an operation, for example for the whole period of an enquiry and a transaction, which might take many minutes.
Although optimistic locking may therefore require extra processing by both, a client and a file server, it can be seen that the technique is far better suited for dealing with relatively dynamic data which may need to be accessed by multiple clients.
When implementing optimistic locking, it is known sometimes to use time stamping to mark data rows in the master database with the time the data was last updated. In this way, if the time stamp for a particular row of data held in a cache is the same as the row in the master database, the file server accepts that the cached data is current and there is no need to re-send the data row in question across the network to the client. Thus, network bandwidth is conserved whenever a cached copy is found to be current.
WO 97/21177 provides a method for checking the consistency of an item of data in a cache database with a respective item of data in a master database by comparing a first key stored in association with the item of data in the cache database with a second key stored in association with an index entry for the respective item of data in the master database. The above mentioned document further provides a method for retrieving an item of data from one of a cache or a master database, the master database comprising a plurality of items of master data and an index containing entries corresponding to one or more of the items of master data, the cache database containing a cache copy of at least one item of the master data.
The method according to the above mentioned document is particularly disadvantageous as it requires the storing of the ‘key’ associated with the cached and master data in a separate data index in order to address, e.g., deleted data items. This increases the overhead of the file server and of the communications between the file server and the requesting clients.
There is a need for an improved method of accessing data in a client-server system.